The technology for digital watermarking media content, such as images, video and audio is well known. A variety of different types of digital watermarks have been developed. Some types of digital watermarks can be read from watermarked data despite changes in the data. For example, some types of image watermarks can survive when the watermarked image is rotated, spatially scaled, lossily compressed, and/or printed. Some video and audio watermarks survive when the watermarked content is lossily compressed, converted to analog form, and re-sampled into digital form.
Some digital watermarks are designed to be fragile so that if the watermarked data is changed the watermark is rendered unreadable or is degraded in a predictable fashion. Such watermarks can be used to determine if a watermarked document has been changed based on detection of the digital watermark. If certain data is watermarked with a fragile watermark, and the data is later changed the watermark is degraded or rendered unreadable. Thus, the absence or degradation of a watermark will indicate that the data has been changed.
Some digital watermarks are designed to be reversible. A watermark is reversible if a data set can be watermarked, thereby changing the data somewhat, and at a later time the watermark can be removed in order to return to the original un-watermarked data set.
The technique used to watermark an image (or data set) determines such factors as: the extent to which a watermark can survive changes in an image, the amount of change in an image needed to destroy a fragile watermark, and how accurately an image can be recreated after a reversible watermark is removed.
One challenge that occurs with some reversible watermarks is that they can cause overflow or underflow conditions. For example, consider a digital image or audio signal that is represented by values from 0 to 255. If during the digital watermarking operation, a digital sample with the value of 254 is increased by 2, there will be an overflow condition. Likewise, if a sample with a value of 1 is decreased by 2, an underflow condition will occur. When an overflow or underflow occurs during a watermarking operation, it poses limitations on the ability to recover the original, un-watermarked signal.
The invention provides a number of methods and related software and systems for embedding auxiliary data in data sets, and for decoding this auxiliary data from the data sets. One aspect of the invention is a method of reversibly embedding auxiliary data in a data set. This method transforms the data set from an original domain into transformed data values with an invertible transform. It expands selected data values to embed auxiliary data. The method then inverts the transformed data values, including the data values selected for expansion, to return the transformed data values to the original domain.
Another aspect of the invention is a compatible decoder for extracting the embedded data and restoring the values of the data set to the same values as before embedding of the auxiliary data. This decoder transforms the data set from an original domain into transformed data values with an invertible transform. It extracts auxiliary data from data values previously selected for embedding of auxiliary data by expansion, and restores the selected data values to the same values as before the embedding of the auxiliary data. It then inverts the transformed data values, including the data values selected for expansion, to return the transformed data values to the original domain.
Another aspect of the invention is a method of reversibly embedding auxiliary data in a data set. This embedding method selects embedding locations in the data set that have a property that is invariant to changes due to embedding of the auxiliary data. The invariant property enables a decoder to identify embedding locations. The embedding method then reversibly embeds auxiliary data into data values at the embedding locations.
Another aspect of the invention is a method of decoding reversibly embedded auxiliary data in a data set. This method identifies a subset of locations in the data set that have a property that is invariant to changes due to embedding of the auxiliary data. It extracts auxiliary data from data values at the identified locations. It then restores values of the data set to the same values as before the embedding of the auxiliary data into the data set.
Another aspect of the invention is a method of embedding auxiliary data in a data set. This method identifies values derived from the data set that are expandable. It expands the identified values by inserting an auxiliary data state corresponding to auxiliary data to be embedded in the identified values. This method has a corresponding decoding method, and can be used for reversible data embedding applications.
Further features will become apparent from the following detailed description and accompanying drawings.